package codetop.microsoft.T450;

import util.TreeNode;

/**
 * @Author: 18362
 * @Create: 2022-08-17 9:33:31 星期三
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return null;
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        }
        if (root.left != null) {
            if (root.left.right != null) {
                TreeNode p = root.left, q = p.right;
                while (q.right != null) {
                    q = q.right;
                    p = p.right;
                }
                q.right = root.right;
                p.right = q.left;
                q.left = root.left;
                root = q;
            } else {
                root.left.right = root.right;
                root = root.left;
            }
            return root;
        } else if (root.right != null) {
            if (root.right.left != null) {
                TreeNode p = root.right, q = p.left;
                while (q.left != null) {
                    q = q.left;
                    p = p.left;
                }
                q.left = root.left;
                p.left = q.right;
                q.right = root.right;
                root = q;
            } else {
                root.right.left = root.left;
                root = root.right;
            }
            return root;
        } else
            return null;
    }
}